'''
Created on Jun 3, 2009

@author: user
'''
import graph
import time
import random
import os
import networkx
def networkx_to_pythongraph_no_weights(networkx_graph):
    new_graph = graph.graph()  
    for node in networkx_graph.nodes():
        new_graph.add_node(node)
    for (u,v) in networkx_graph.edges():
        new_graph.add_edge(u,v)
    return new_graph

def powerset(values):
    if len(values) <= 1:
        yield values
        if len(values)>0: # Added if to solve bug for powerset([]), i.e. values=[]
            yield[]
    else:
        for item in powerset(values[1:]):
            yield [values[0]]+item
            yield item
            
def list_set_equals(list1,list2):
    ''' List equals that assumes the lists don't have duplicate nodes '''
    return set(list1)==set(list2)

def import_graph(graph_file_name,file_format='xml'):
    ''' Import a graph from a file '''
    
    graph_file = open(graph_file_name,"r+")
    read_xml = graph_file.read()
    graph_file.close()
    imported_graph = graph.graph()
    imported_graph.read(read_xml,file_format)
    return imported_graph

def convert_node_names_to_numbers(source_graph):
    ''' Create a graph that is equal to the source graph, except that all the names of the nodes are integers '''
    converted_graph = graph.graph()
    nodelist = [int(node) for node in source_graph.nodes()]
    converted_graph.add_nodes(nodelist)

    for each_node in source_graph.nodes():
        for each_edge in source_graph.neighbors(each_node):
            converted_graph.add_edge(int(each_node), int(each_edge))    
    return converted_graph
    
def export_graph(exp_graph,current_graph_file, file_format='xml'):
    ''' Export a graph to a file '''
    graph_xml = exp_graph.write(file_format)
    graph_file = open(current_graph_file,"w+")
    graph_file.write(graph_xml)
    graph_file.close()
'''
def len_nodes(a_graph):
    return len(a_graph)
def len_edges(a_graph):
    return len(self.edge_properties)
''' 
       
def graphs_equal(graph1,graph2):
    ''' Currently ignores direction of edges and weights '''
    ''' Currently assumes no self or duplicate edges '''
        
    # Check equal num. of nodes
 
    if len(graph1)!=len(graph2):
        return False

    # Check equal num. of edges
    edges1 = graph1.edges()
    edges2 = graph2.edges()
    if len(edges1)!=len(edges2):
        return False
    
    # Check nodes are the same and have same neighbors
    nodes1 = graph1.nodes()
    nodes2 = graph2.nodes()      
    for node in nodes1:
        if node not in nodes2:
            return False
        neighbors = graph1.neighbors(node)

        if len(neighbors)!=len(graph2.neighbors(node)):
            return False

        for neighbor in graph1[node]:
            if graph2.has_edge(node, neighbor)==False:
                return False
    
    return True
    
def stdev(values):
    ''' Computes the standard deviation of a list of values '''
    count = len(values)
    average = float(sum(values))/count
    return sum([abs(value-average) for value in values])/count


def backup_old_file(output_file_name,backup_dir="backup",backup_suffix=".backup"):
    ''' Create a backup of an existing file with the same name as output_file_name '''
    
    if os.path.isdir(backup_dir)==False:
        os.mkdir(backup_dir)
    
    if os.path.isfile(output_file_name) == True:
        counter = 1
        backup_output_file = os.path.join(backup_dir,os.path.basename(output_file_name) + str(counter) + backup_suffix)
        while os.path.isfile(backup_output_file):
            counter = counter + 1
            backup_output_file = backup_output_file = os.path.join(backup_dir,os.path.basename(output_file_name) + str(counter))
        
        os.rename(output_file_name, backup_output_file)

def choose_random_node(a_graph):
    ''' Chooses a random node from the graph '''
    nodes = a_graph.nodes()
    return nodes[random.randint(0,len(nodes)-1)]

def factorial(n):
    """factorial(n): return the factorial of the integer n.
    factorial(0) = 1
    factorial(n) with n<0 is -factorial(abs(n))
    """
    result = 1
    for i in xrange(1, abs(n)+1):
        result *= i
    if n >= 0:
        return result
    else:
        return -result

def binomial(n, k):
    """binomial(n, k): return the binomial coefficient (n k)."""
    assert n>0 and isinstance(n, (int, long)) and isinstance(k, (int,long))
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return factorial(n) // (factorial(k) * factorial(n-k))

